《剑指offer》 13.机器人的运动范围

剑指offer
留言

note:此类型题目（路径搜索）一般深度优先搜索和广度优先搜索是最优解。方向数组也是常用的小技巧。

题目描述

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1
2
输入：m = 2, n = 3, k = 1
输出：3

示例 2：

1
2
输入：m = 3, n = 1, k = 0
输出：1

提示：

  • $1 <= n,m <= 100$
  • $0 <= k <= 20$

方法一：深度优先搜索

思路

这道题和12题十分类似，也是一个矩阵，但是不同之处在于12题要求搜索一个字符串，本题确实要求你找可达范围。注意题目中，不能进入行坐标和列坐标数位之和大于k的格子这句条件。这句条件其实是帮助我们给定了一个递归边界。或者说，对于路径搜索类的题目，这句话其实是给了障碍物的所在。

先讨论这个条件如何计算，如果仅仅针对这道题，也就是$1<=n,m<=100$，在这种情况下，坐标$i,j$的大小在0-99之间，计算是非常方便的$i\%10+i/10+j\%10+j/10$就是我们需要的数位之和。

如果题目没有给出限制，我们就需要来写一个函数进行处理，比如

1
2
3
4
5
6
7
8
int sumfun(int i){
	int sum=0;
	while(i>0){
		sum += i%10;
		i /= 10; 
	}
	return sum;
}

最后的结果就是sumfun(i)+sumfun(j)。

然后分析我们的递归函数如何写，递归的思想就是将大问题，分解成子问题，最重要的就是如何把握递归边界，如何进行合理剪枝（访问过的不要再访问）。访问过的不要再访问这一个需求，就需要我们建立一个二维数组，来记录是否访问。不同于12题中回溯的做法，我们该题目中问的问题是所能到达的所有格子，所以我们不需要进行回退操作，那样会导致重复计算。

  • 递归边界：显然首先是$i,j$不能超出矩阵；其次是$i,j$不能走到障碍物上；最后就是访问过的不能再访问以防止重复计算
  • 递归过程：修改访问矩阵，表明某个格子已经访问过了；然后递归求解子问题，即向四周进行递归，这里存在一个优化，就是由于我们从（0，0）开始，所以我们开始都是向右、或者向下走，然后由于障碍物跟行列坐标息息相关，很容易发现，所有的障碍物格子，都可以由左方或上方的格子移动一步得到，因此我们可以将搜索方向缩减为向右或向下（具体参考力扣题解中的动图）；最后要在向左、向下两个子问题的结果上再加一，表示该层递归格子本身也是一个可访问的格子。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int num=0;
    int dfs(vector<vector<int>> &map,int i,int j,int m,int n,int k){
        int sum=0;
        if(i<0 || i>=m || j<0 || j>=n || i%10+i/10+j%10+j/10 > k || map[i][j]==1)
            return 0;
        map[i][j]=1;
        sum = 1 + dfs(map,i+1,j,m,n,k) + dfs(map,i,j+1,m,n,k);
        //map[i][j]=0;
        return sum;
        
    }
public:
    int movingCount(int m, int n, int k) {
        vector<vector<int>> map(m,vector<int>(n,0));
        int ans=0;
        ans = dfs(map,0,0,m,n,k);

        return ans;
    }
};

复杂度分析

  • 时间复杂度$O(MN)$。此处的$MN$分别表示$m$和$n$。因为显然我们整个矩阵中的每个元素都要进入递归，来看一下是否满足需求。
  • 空间复杂度$O(MN)$。因为我们需要创建一个矩阵来记录每个格子是否访问过。

方法二：广度优先搜索

思路

广度优先搜索是使用队列这一数据结构进行搜索的。每次访问到一个格子，要做到以下几步操作：

  • 从队列首取出某个格子，出队，分别访问它的右、下两个格子
  • 如果这个格子符合要求（不超边界、非障碍、未访问），将这个格子放入队列中，
  • 将这个格子标记为已访问
  • 可访问格子数增加。

广度优先搜索和深度优先搜索的主要区别是一个是把同层的全部进行访问后再访问下一层，另一个是一直向下访问直到走不动再回去访问下一个。

这里还有一个小技巧是方向数组，经常用在搜索算法中，在C/C++中可以用二维数组来表示方向。例如二维数组a[x][y]含义就是方向数组中存放了x个向量，y表示每个向量有有y维（y一般为2）。比如我们要访问右边和下边的格子，就是向右方下方移动，所以可以设置二维数组d[2][2] = {(0,1),(1,0})。这个由于方向简单，也可以写为dx[2] = {0,1},dy[2]={1,0}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int movingCount(int m, int n, int k) {
        if(!k) return 1;
        queue<pair<int,int>> que;
        que.push(make_pair(0,0));
        vector<vector<int>> visited(m,vector<int>(n,0));
        visited[0][0] = 1;
        
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        int ans=1;
        while(!que.empty()){
            auto [x,y] = que.front();

            que.pop();

            for(int i=0;i<2;i++){
                int tx = x + dx[i];
                int ty = y + dy[i];
                if(tx<0 || tx>=m || ty<0 || ty>=n || tx%10+tx/10+ty%10+ty/10>k||visited[tx][ty]==1) continue;
                que.push(make_pair(tx,ty));
                visited[tx][ty] = 1;
                ans++;
            }

        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度$O(MN)$。同样我们需要访问数组的所有格子。
  • 空间复杂度$O(MN)$。同样我们需要记录访问过的格子。当然还有一个空间就是队列的空间，该空间同样是$MN$的复杂度

方法三： 递推

思路

我们提到我们的搜索方向只有向下或者向右，那么也就是说每个格子是否可达其实依赖于它的上方或者左方是否可达，我们可以得到一个递推关系式，即：

当然这是在不考虑障碍物的情况，所以我们可以根据递推关系式和障碍物的条件，推出整个visited矩阵的情况，在同一时间，我们就也得到了可达的格子数目。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int movingCount(int m, int n, int k) {
        if(!k)
            return 1;
        vector<vector<int>> visited(m,vector<int>(n,0));

        visited[0][0] = 1;
        int ans = 1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0 || i%10+i/10+j%10+j/10>k) continue;
                if(i-1>=0) visited[i][j] |= visited[i-1][j];
                if(j-1>=0) visited[i][j] |= visited[i][j-1];
                ans += visited[i][j];
            }
        }
        return ans;
    }
};=

复杂度

  • 时间复杂度$O(MN)$。同样需要遍历所有的格子
  • 空间复杂度$O(MN)$。同样需要同样大小的存储空间，但是此方法不需要队列的存在，也不需要递归的空间。所以空间上来说是更优的。